"""
给定两个字符串 s 和 t，它们只包含小写字母。
字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
请找出在 t 中被添加的字母。
示例 1：
输入：s = "abcd", t = "abcde"
输出："e"
解释：'e' 是那个被添加的字母。

测试用例1：
输入：s = "ae", t = "aea"
预期输出："a"

测试用例2：
输入：s = "def", t = "deff"
预期输出："f"

测试用例3：
输入：s = "xy", t = "xyz"
预期输出："z"
"""

from collections import defaultdict

def p1(s, t):
    table = defaultdict(int)
    
    for c in s:
        table[c] += 1
        
    
    for c in t:
        if c in table:
            table[c] -= 1
            if table[c] < 0:
                return c
        else:
            return c


if __name__ == "__main__":
    s = "xy"
    t = "xyz"
    print(p1(s, t))
